package cxydmmszl.chapter04.t074;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 跳跃游戏
 * <li style="color: green;">Desc</li>
 * 给定数组 arr，arr[i]==k 代表可以从位置向右跳 1~k 个距离。
 * 比如，arr[2]==3，代表可以从位置 2 跳到位置 3、位置 4 或位置 5。
 * 如果从位置 0 出发，返回最少跳几次能跳到 arr 最后的位置上。
 * <li style="color: green;">Input</li>
 * 输出包括两行，第一行一个整数 n(1≤n≤1e5)，代表 arr 数组长度，
 * 第二行 n 个整数代表数组 arr[i](1≤arr[i]≤n)。
 * <li style="color: green;">Output</li>
 * 输出一个整数，代表最少跳的次数。
 * <li style="color: blue;">Link</li> CD92
 *
 * @author habitplus
 * @since 2021-09-23 10:32
 */
public class Main {
    static StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        int step = jumpGame(arr);
        System.out.println(step);
    }

    private static int jumpGame(int[] arr) {
        if (arr == null || arr.length < 2) return 0;

        // 目前已跳的步数
        int jump = 0;
        // 如果只能跳 jump 步，最远能到达的位置
        int cur = 0;
        // 如果再多跳一步，最远能到达的位置
        int next = 0;

        for (int i = 0; i < arr.length; i++) {
            if (cur < i) {
                jump++;
                cur = next;
            }
            next = Math.max(next, i + arr[i]);
        }

        return jump;
    }

}
